/*
 * @lc app=leetcode.cn id=788 lang=javascript
 *
 * [788] 旋转数字
 */

// @lc code=start
/**
 * @param {number} N
 * @return {number}
 */
var rotatedDigits = function(N) {
    let set=new Set([2,5,6,9])
    let set_no=new Set([4,7,3])
    let count=0
    let i=1
    while(i<=N){
        let temp=i.toString().split("")
        if(temp.some((item)=>{return set.has(+item)})&&temp.every((item)=>{return !set_no.has(+item)}))count++
        i++
    }
    return count
};
// @lc code=end

var rotatedDigits = function(N) {
    let ans = 0
    const d = [0, 0, 1, -1, -1, 1, 1, -1, 0, 1].concat(Array(Math.max(0, N - 9)).fill(0))
    for (let i = 0; i <= N; ++i) {
        if (d[Math.floor(i / 10)] == -1 || d[i % 10] == -1) {//去除坏数,保留普数和好数再次判断
            d[i] = -1
        } else if (d[Math.floor(i / 10)] == 1 || d[i % 10] == 1) {//普数和好数的组合。可能前面位数是普数，新加一位好数等等
            d[i] = 1
            ++ans
        }
    }
    return ans
};//思路就是除了末尾以外的数字肯定计算过，只要除末尾的数和之前的数存在一个好数，那么就是好数，所以动态规划判断即可。